@MastersThesis{Almeida:2009:MéHePr,
               author = "Almeida, Wesley Gomes de",
                title = "M{\'e}todos heur{\'{\i}}sticos para o problema de 
                         localiza{\c{c}}{\~a}o de concentradores",
               school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
                 year = "2009",
              address = "S{\~a}o Jos{\'e} dos Campos",
                month = "2009-02-27",
             keywords = "problema de localiza{\c{c}}{\~a}o de concentradores, 
                         metaheur{\'{\i}}stica, algoritmo gen{\'e}tico, lista tabu, 
                         recozimento simulado, busca por agrupamentos, hub location 
                         problem, metauristic, genetic algorithm, tabu list, simulated, 
                         annealing, clustering search.",
             abstract = "O problema de localiza{\c{c}}{\~a}o de concentradores (hubs) 
                         {\'e} comumente encontrado em redes de transporte e de 
                         telecomunica{\c{c}}{\~a}o. Trata-se de problema de 
                         Otimiza{\c{c}}{\~a}o Combinat{\'o}ria NP-dif{\'{\i}}cil e que 
                         ocorre em diversas situa{\c{c}}{\~o}es pr{\'a}ticas, tais como: 
                         no transporte a{\'e}reo, nos servi{\c{c}}os de entregas postais, 
                         nos servi{\c{c}}os de atendimento de emerg{\^e}ncia, no 
                         abastecimento de supermercados e de redes de lojas, na 
                         localiza{\c{c}}{\~a}o de antenas de comunica{\c{c}}{\~a}o, 
                         dentre muitas outras. A decis{\~a}o sobre a 
                         localiza{\c{c}}{\~a}o de concentradores e quais os n{\'o}s da 
                         rede ser{\~a}o alocados a cada um destes, depende do n{\'u}mero 
                         de concentradores necess{\'a}rios, da demanda de cada um dos 
                         n{\'o}s, da capacidade de atendimento dos concentradores, dentre 
                         outros fatores. Metaheur{\'{\i}}sticas t{\^e}m sido usadas com 
                         sucesso para obter solu{\c{c}}{\~o}es em diversos problemas de 
                         Otimiza{\c{c}}{\~a}o Combinat{\'o}ria. No entanto, a 
                         constru{\c{c}}{\~a}o de algoritmos heur{\'{\i}}sticos 
                         eficientes requer bons mecanismos de intensifica{\c{c}}{\~a}o de 
                         busca. Neste trabalho estuda-se o problema de 
                         localiza{\c{c}}{\~a}o de concentradores e prop{\~o}em-se 
                         m{\'e}todos heur{\'{\i}}sticos que utilizam a busca por 
                         agrupamentos, uma t{\'e}cnica de intensifica{\c{c}}{\~a}o de 
                         busca capaz de identificar as regi{\~o}es do espa{\c{c}}o de 
                         busca mais promissoras para a obten{\c{c}}{\~a}o de boas 
                         solu{\c{c}}{\~o}es. S{\~a}o propostos um algoritmo 
                         gen{\'e}tico (AG) e um algoritmo simulated annealing com lista 
                         tabu (SATL). Testes computacionais foram realizados com os 
                         algoritmos propostos e com estes algoritmos combinados com a busca 
                         por agrupamentos (clustering search). Os testes demonstram que a 
                         aplica{\c{c}}{\~a}o da busca por agrupamentos a estes algoritmos 
                         permite obter solu{\c{c}}{\~o}es de melhor qualidade e em menor 
                         tempo computacional, em rela{\c{c}}{\~a}o {\`a}s 
                         solu{\c{c}}{\~o}es obtidas pelos algoritmos AG e SATL 
                         isoladamente. ABSTRACT: The hub location problem is commonly found 
                         in transport networks and in telecommunications networks. It is a 
                         NP-hard Combinatorial Optimization problem that occurs in many 
                         practical situations, such as air transport, services of postal 
                         deliveries, emergency care services, supplying networks of 
                         supermarkets and shops, location of antennas for communication, 
                         among many others. The decision about the hubs location and for 
                         which hub the other network nodes should be allocated depends of 
                         the number of hubs needed, the demand of each node, the service 
                         capacity of the hubs, among other factors. Metaheuristcs have been 
                         used successfully to obtain solutions to various Combinatorial 
                         Optimization problems. However, the construction of efficient 
                         heuristics requires good search intensification mechanisms. In 
                         this work the hub location problem is studied and heuristic 
                         methods are proposed. The proposed methods use the clustering to 
                         identify the regions of the search space which are more promising 
                         for obtaining good solutions. Two algorithms are proposed: a 
                         genetic algorithm (AG) and a simulated annealing with tabu list 
                         algorithm (SATL). Computational tests were accomplished with the 
                         proposed algorithms and with these algorithms combined with the 
                         clustering search. The tests demonstrate that the application of 
                         the clustering search to these algorithms allows to obtain 
                         solutions of better quality and in smaller computational times, in 
                         relation to the solutions obtained by the algorithms AG and SATL 
                         separately.",
            committee = "Yanasse, Horacio Hideki (presidente) and Senne, Edson Luiz 
                         Fran{\c{c}}a (orientador) and Pereira, Marcos Antonio and 
                         Goldbarg, Marco Cesar",
           copyholder = "SID/SCD",
         englishtitle = "Heuristic methods for the location problem",
             language = "pt",
                pages = "112",
                  ibi = "8JMKD3MGP8W/34PGRBS",
                  url = "http://urlib.net/ibi/8JMKD3MGP8W/34PGRBS",
        urlaccessdate = "08 maio 2024"
}